package leetcode.tree.binary.balance;

import leetcode.tree.binary.TreeNode;

/**
 * 110. 平衡二叉树
 *
 * 判断一颗树是否为平衡二叉树
 *
 */
public class IsBalanced {

    public static void main(String[] args) {
        IsBalanced solution = new IsBalanced();

        boolean res = solution.isBalanced(solution.createTree());
        System.out.println(res);
    }

    public TreeNode createTree() {
        TreeNode root = new TreeNode(1);
        TreeNode node1 = new TreeNode(2);
        TreeNode node2 = new TreeNode(2);
        root.left = node1;
        root.right = node2;
        return root;
    }

    /**
     * 使用递归 自己写的 和官方的思路一样
     *
     * 分别对左右子树递归求高度, 然后进行对比
     *
     * @param root 树对象
     * @return
     */
    public boolean isBalanced0(TreeNode root) {
        return treeHeight(root) >= 0;
    }

    /**
     * 求树的高度  -1表示不是平衡二叉树
     *
     * @param root 树对象
     * @return
     */
    public int treeHeight(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftHeight = treeHeight(root.left);
        if (leftHeight == -1) {
            return -1;
        }
        int rightHeight = treeHeight(root.right);
        if (rightHeight == -1) {
            return -1;
        }
        if (Math.abs(leftHeight - rightHeight) > 1) {
            return -1;
        }
        return Math.max(leftHeight, rightHeight) + 1;
    }


    /**
     * 自底向上递归遍历 类似后序遍历
     *
     * 官方写法
     *
     * @param root 树对象
     * @return
     */
    public boolean isBalanced(TreeNode root) {
        return height(root) >= 0;
    }

    /**
     * 递归方法
     *
     * 判断当前树的高度
     *
     * @param root 当前树对象
     * @return  树的高度  -1表示不是平衡二叉树
     */
    public int height(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftHeight = height(root.left);
        int rightHeight = height(root.right);
        if (leftHeight == -1 || rightHeight == -1 || Math.abs(leftHeight - rightHeight) > 1) {
            return -1;
        } else {
            return Math.max(leftHeight, rightHeight) + 1;
        }
    }

}
